/**
 * @file cx_heap.c
 * @author Char_X (2421498578@qq.com)
 * @brief Implementation of memory management
 * @version 0.1 
 * @date 2023-03-19 Basic function of memory management by lists use macro CX_LIB_DISABLE_HEAP to disable default heap management
 * @note If you use disable macro, the cx_heap_init() function will invalid 
 *       and you should use x_heap_override_manager()to override manager function
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include "cx_heap.h"

#include "stdio.h"

// #define NULL (void *)0
#define CX_SIZE_T_BITS 32                                        // indicates contain bits of the size_t type
#define CX_MEMORY_ALLOCATED_MASK (0x01 << (CX_SIZE_T_BITS - 1)); // indicates if a memory block allocated
__attribute__((used)) static cx_os_sem_t cx_head_sem = NULL;

static void cx_heap_free(void * ptr);
static void * cx_heap_malloc(cx_size_t size);

struct external_hook
{
    void (*StopScheduler)(void);
    void (*StartScheduler)(void);
    void (*mallocError)(void);
    void (*freeError)(void);
};

/*CX heap manager interface*/
void *(*real_malloc)(cx_size_t size) = cx_heap_malloc;
void (*real_free)(void *ptr) = cx_heap_free;


static unsigned char *cx_heap_pool = NULL;
static cx_size_t cx_heap_pool_size = 0;

static cx_size_t cx_heap_free_size = 0;
// static cx_int32_t cx_heap_initialized = 0;

cx_BlockLink_t *cx_heap_start;
cx_BlockLink_t *cx_heap_end;

int cx_heap_override_manager(void* (*malloc)(cx_size_t), void (*free)(void*))
{
    real_malloc = malloc;
    real_free = free;
    return 0;
}

void *cx_malloc(cx_size_t size)
{
    return real_malloc(size);
}

void cx_free(void* ptr)
{
    real_free(ptr);
}

cx_int32_t cx_heap_init(cx_byte * pool, cx_size_t size)
{
    cx_heap_pool = pool;
    cx_heap_pool_size = size;

    cx_heap_start = (cx_BlockLink_t *)cx_heap_pool;
    cx_heap_end   = (cx_BlockLink_t*)((cx_uintptr_t)cx_heap_pool + size - sizeof(cx_BlockLink_t));

    cx_heap_end->BlockSize = 0;
    cx_heap_end->NextFreeBlock = NULL;

    cx_heap_start->NextFreeBlock = cx_heap_end;
    cx_heap_start->BlockSize     = cx_heap_pool_size - (sizeof(cx_BlockLink_t) * 2);

    cx_heap_free_size = cx_heap_start->BlockSize;
    return cx_heap_free_size;
}

/**
 * @brief foreach free block and merge those continuious blocks
 * 
 * @return cx_size_t total bytes of merged blocks
 */
static cx_size_t MergeFreeBlock(void)
{
    cx_size_t total_merged = 0,merge_size;
    cx_BlockLink_t *cur = cx_heap_start;
    while(cur->NextFreeBlock != NULL)
    {
        if(((cx_uintptr_t)cur) + cur->BlockSize + sizeof(cx_BlockLink_t) == ((cx_uintptr_t)(cur->NextFreeBlock)))
        {
            merge_size = cur->NextFreeBlock->BlockSize + sizeof(cx_BlockLink_t);
            total_merged += merge_size;
            cur->BlockSize += merge_size;
            cur->NextFreeBlock = cur->NextFreeBlock->NextFreeBlock;
        }
        else
        {
            cur = cur->NextFreeBlock;
        }
    }
    return total_merged;
}

/**
 * @brief Insert the block who was freed into the free block list
 * 
 * @param block pointer need to be inserted 
 */
static void InsertFreeBlock(cx_BlockLink_t *block)
{
    cx_BlockLink_t *seek = cx_heap_start;
    // if seek if before start of block, insert it directly
    if((cx_uintptr_t)block < (cx_uintptr_t)seek)
    {
        block->NextFreeBlock = seek;
        cx_heap_start = block;
    }
    else
    {
        // while(seek != NULL)
        // {
        //     if(((cx_uint)seek_previous) < ((cx_uint)block) && ((cx_uint)seek) > ((cx_uint)block))
        //     {
        //         seek_previous->NextFreeBlock = block;
        //         block->NextFreeBlock = seek;
        //     }
        //     else
        //     {
        //         seek_previous = seek;
        //         seek = seek->NextFreeBlock;
        //     }
        // }
        while(seek->NextFreeBlock != NULL)
        {
            if(((cx_uintptr_t)block) > ((cx_uintptr_t)seek) && ((cx_uintptr_t)block) < ((cx_uintptr_t)(seek->NextFreeBlock)))
            {
                block->NextFreeBlock = seek->NextFreeBlock;
                seek->NextFreeBlock = block;
            }
            else
            {
                seek = seek->NextFreeBlock;
            }
        }
    }
}

static void * cx_heap_malloc(cx_size_t size)
{
    cx_BlockLink_t *seek = cx_heap_start, *seek_previous = cx_heap_start, *new_free_block;
    cx_size_t need_mem = sizeof(cx_BlockLink_t) + size;
    CX_OS_SEM_WAIT(cx_head_sem);
    while(seek != NULL)
    {
        if(seek->BlockSize >= size)
        {
            break;
        }
        else
        {
            seek_previous = seek;
            seek = seek->NextFreeBlock;
        }
    }
    if(seek == NULL)
    {
        return NULL;
    }
    else
    {
        if((seek->BlockSize - size) <= sizeof(cx_BlockLink_t))
        {
            // need_mem = seek->BlockSize;
            new_free_block = seek->NextFreeBlock;
        }
        else
        {
            new_free_block = ((cx_BlockLink_t*)(((cx_uintptr_t)seek) + need_mem));
            new_free_block->NextFreeBlock = seek->NextFreeBlock;
            new_free_block->BlockSize = seek->BlockSize - need_mem;
            seek->BlockSize = size;
        }
        seek->BlockSize |= CX_MEMORY_ALLOCATED_MASK;
        if((cx_uintptr_t)seek != (cx_uintptr_t)cx_heap_start)
        {
            seek_previous->NextFreeBlock = new_free_block;
        } 
        else
        {
            cx_heap_start = new_free_block;
        }
    }
    CX_OS_SEM_SIGNAL(cx_head_sem);
    return (void *)(((cx_uintptr_t)seek) + sizeof(cx_BlockLink_t));
}

static void cx_heap_free(void * ptr)
{
    cx_BlockLink_t *NeedToFreeBlock = (cx_BlockLink_t*)(((cx_uintptr_t)ptr) - sizeof(cx_BlockLink_t));
    CX_OS_SEM_WAIT(cx_head_sem);
    NeedToFreeBlock->BlockSize &= ~CX_MEMORY_ALLOCATED_MASK;
    InsertFreeBlock(NeedToFreeBlock);
    MergeFreeBlock();
    CX_OS_SEM_SIGNAL(cx_head_sem);
}

cx_size_t cx_getHeapBlockSize(void *ptr)
{
    cx_BlockLink_t *block = (cx_BlockLink_t*)(((cx_uintptr_t)ptr) - sizeof(cx_BlockLink_t));
    block->BlockSize &= ~CX_MEMORY_ALLOCATED_MASK;
    return block->BlockSize;
}
